The development of the EDVAC computer system of 1948 is often cited as the beginning of the computer era. Since that time, computer systems have evolved into extremely sophisticated devices. However, even today's most sophisticated computer systems continue to include many of the basic elements that were present in some of the first computer systems. Two such elements are the computer system's processor and memory. A computer system's processor is the intelligent portion of the computer system. The processor is responsible for executing programs that interpret and manipulate information that is given to the computer system by the computer system's user or users.
As is well known, this information (called data) is stored in the computer system's memory. Computer system memory is generally categorized into two types. While there are various names used to characterize these two basic types of computer system memory, the terms used in this patent document are "main memory" and "auxiliary storage." Computer system information is located using what are called "memory addresses." Information stored in main memory is located via addresses known as real addresses, while information stored in auxiliary storage is located in a way that is specific to the particular type of auxiliary storage device. In general, main memory is used by the computer system to store information that is of current interest to the programs executing on the computer system's processor. Auxiliary storage, on the other hand, is used to store information that is not currently needed by the programs.
Over the years, computer system designers have created numerous types of addressing schemes. While these addressing schemes are quite complicated and vary to a large degree, most modern day addressing schemes share the concept of "virtual addressing." At the most fundamental level, virtual addressing allows most programs to operate without having to understand whether needed information is stored in main memory or in auxiliary storage. In other words, virtual addressing allows programs to locate and access needed information through a single virtual address regardless of whether the information is actually stored in main memory or in auxiliary storage. When taken together, the virtual addresses of a computer system are said to form the computer system's virtual address space, or just address space for short.
In operation, a program that needs to gain access to a particular piece of information presents the virtual address to the computer system. The computer system first checks to see if the information is available in main memory. The computer system does this by attempting to translate the presented virtual address into a real address. If the translation is successful, the computer system simply allows the program to go ahead and access the information using the real address. However, if the translation fails, the computer system's processor knows that it cannot access the information directly. Therefore, the computer system will move the needed information from auxiliary storage into main memory (if necessary), translate the virtual address into a real address, and then allow the program to access the information using the real address. It should be pointed out here that the time it takes for a computer system to translate a virtual address into a real address is a key factor in overall system performance. It is desirable to take as little time as possible to make the translation because the longer it takes, the longer the requesting program has to wait for its information. Therefore, computer system designers are continually working on ways to speed up address translation.
As time passes, minimizing address translation time is becoming increasingly difficult because computer systems are designed with more and more virtual addresses so that they can handle more and more information. The difficulty arises because the larger the address space, the more difficult it is to manage, control, and coordinate how all those individual addresses are used by programs. One way to at least help organize the problem of managing a large address space is to break up the addresses into logical ranges of addresses. These ranges are sometimes called "virtual memory partitions" or "virtual memory segments." The virtual partitions or segments are then typically further broken into smaller ranges called "virtual memory pages." For readability, the word "virtual" is dropped during much of the ensuing discussion. Unless otherwise qualified, words and phrases such as address, memory page and segment should be taken to refer to virtual addresses, memory pages, and/or segments. When a program wants to store information, it requests allocation of a segment.
The management of these segments and pages is commonly facilitated through the use of address translation tables (sometimes called "page tables"). Address translation tables typically include entries that are used to convert virtual addresses into real addresses (i.e., each entry includes a virtual address and the associated real address). If a presented virtual address can be found in the translation table, it can be translated into a real address.
However, the way in which today's address tables are designed and managed has become a serious impediment to the continued reduction of address translation time. The translation time problem is caused by the combination of two factors. The first factor is the fundamental way in which address translation tables are usually designed. Address translation tables are typically designed such that specific portions of the table are reserved for specific sets of virtual addresses, which means that each reserved portion becomes a table unto itself (a minitable if you will). The second factor is the basic way in which programs tend to behave relative to virtual memory segments. It has been observed that segments that are allocated in close time proximity tend to be used in close time proximity. These two factors combine to cause clumping in the address translation table because the table entries end up being either logically or physically very close to one another. In other words, some of the minitables become full or over utilized, while others are unused or under utilized. The clumping in turn causes a slow down in average address translation time because the computer system must always sift through all the table entries in a full or nearly full minitable every time it needs to translate a presented virtual address into a real address.
Without a mechanism that reduces address translation time and thereby reduces the associated performance cost to executing programs, computer systems will never fully realize the benefits of virtual addressing.